Міністерство науки і освіти України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
кафедра програмного забезпечення
Звіт з лабораторної роботи №11
з дисципліни “Алгоритми і структури даних ”
Виконав:
студент групи ПІ – 1
Львів 2008
Тема роботи: Ознайомлення із методами пошуку. Алгоритм Кнута-Моріса-Прата.
Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із алгоритмом Кнута-Моріса-Прата. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема алгоритму Кнута-Моріса-Прата.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Алгоритм Кнута-Моріса-Прата (англ. Knuth–Morris–Pratt algorithm) шукає входження слова W у рядку S використовуючи просте спостереження, що коли відбувається невідповідність, то слово містить у собі достатньо інформації, для того щоб визначити, де наступне входження може початися, таким чином пропускаючи кілька разову перевірка попередньо порівняних символів.
Алгоритм був винайдений вченими Donald Knuth та Vaughan Pratt і незалежно J. H. Morris у 1977 році, але був опублікований у спільній статті.
Маємо масив символів S з n елементів (текст) та масив P з m - взірець. Необхідно знайти перше входження взірця в масив. Схема алгоритму полягає у поступовому порівнянні взірця з текстом та зсуву по тексту на кількість співпавших символів у разі знайденого неспівпадіння.
Алгоритм КМП
КМП1. Встановити і=0.
КМП2. j=0, d=1.
КМП2. Поки j<m, i<n
КМП 3. Перевірка: якщо s[i]=p[j], то d++, i++.j++ поки d != m.
Інакше встановити зсув взірця на d позицій по тексту. Перейти на крок КМП2.
КМП4. Кінець.
Складність алгоритму становить O(n+m).
Приклад,
Hoola-Hoola girls like Hooligan - текст
Hooligan – взірець
Hoola-Hoola girls like Hooligan
Hooligan i!=a, d=4
Hooligan H!=a, d=1
Hooligan H!=-, d=1
Hooligan i!=a, d=4
…..
Hooligan d=m=8
Текст програми
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<string.h>
//-----------------------------------------------------------------------
int max(int mas[],char t[])
{
int i,max=mas[0];
for(i=1; i<signed(strlen(t)); i++)
if(mas[i]>max) max=mas[i];
return max;
}
//-----------------------------------------------------------------------
void main()
{
char s[100],t[10];
int i,j,a,D,d=1,pos;
int mas[10];
puts("Vvedit text:");
gets(s);
puts("Vvedit ekzemplyar:");
scanf("%s", &t);
/*-Заповнення таблиці-*/
for(j=strlen(t)-1; j>=0; j--)
{
a=0;
for(i=j-1;i>=0;i--)
if(t[i]==t[j])
{
a++;
mas[j]=j-i;
i=-1;
}
if(a==0) mas[j]=0;
}
D=max(mas,t);
j=0;
while(i<signed(strlen(s)))
{
if(s[i]==t[j])
{
if(j==0) pos=i+1;
if(j==signed(strlen(t)-1)) i=strlen(s);
i++;
j++;
d++;
}
else
{
if(d>D) d=D;
i+=d;
j=0;
pos=0;
}
}
if(pos==0) puts("Spivpadinnya nemaye!");
else printf("Pershe vhodgennja - %i",pos);
getch();
}
Протокол роботи програми
Висновок: Вивчив та дослідив методи пошуку, як один із методів обробки даних. Ознайомився із алгоритмом Кнута-Моріса-Прата. Виконав лабораторну роботу використавши здобуті знання з методів пошуку, зокрема алгоритму Кнута-Моріса-Прата.
